#include <iostream>
using namespace std;

#include "ProgCommon.h"
#include "Array2D.h"


int Knapsack( int n, int C, int ts[], int tv[] )
{
    int i, j, k, volume, value, mx, tmp;
    Array2D<int> V( n+1, C+1 );

    for ( i = 0; i <= n; i++ ) {
        V[i][0] = 0;
    }
    for ( j = 0; j <= C; j++ ) {
        V[0][j] = 0;
    }

    for ( i = 1; i <= n; i++ ) {
        for ( j = 1; j <= C; j++ ) {
            V[i][j] = V[i-1][j];
            volume = ts[i];
            value = tv[i];
            if ( volume <= j ) {
                mx = V[i][j];
                for ( k = 0; k <= j/volume; k++ ) {
                    tmp = V[i-1][j-k*volume] + k*value;
                    if ( tmp > mx )
                        mx = tmp;
                }
                V[i][j] = mx;
            }
        }
    }

    cout << V << endl;

    return V[n][C];
}


int main()
{
    PROG_BANNER;

    int n = 4;
    int C = 9;
    int ts[] = { -1, 2, 3, 4, 5 };
    int tv[] = { -1, 3, 4, 5, 7 };

    ConSetColor( FG_CYAN );
    printf( "Prog 5: Full Knapsack\n" );
    ConSetColor( COLOR_DEFAULT );

    printf( " * DP matrix >>\n\n" );

    ConSetColor( FG_GREEN );
    int val = Knapsack( n, C, ts, tv ); // 13
    ConSetColor( COLOR_DEFAULT );

    printf( "Final value is: ");
    ConSetColor( FG_RED );
    printf( "%d", val );
    ConSetColor( COLOR_DEFAULT );

    printf( "\n" );
    PROG_BANNER;
    PROG_PAUSE;
    return 0;
}


